package Demo01;

import org.omg.CORBA.CODESET_INCOMPATIBLE;

import java.util.List;

public class MyList implements Ilist{
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        if(head==null) {
            head = newNode;
        } else {
            ListNode curNode = head;
            while (curNode.next!=null) {
                curNode = curNode.next;
            }
            curNode.next = newNode;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        ListNode newNode = new ListNode(data);
        if(index<0||index>size()) {
            System.out.println("插入下标违法");
            return;
        }
        if(index==0) {
            addFirst(data);
        } else {
            int count = 0;
            ListNode curNode = head;
            while(count+1!=index) {
                curNode = curNode.next;
                count++;
            }
            ListNode tmp = curNode.next;
            curNode.next = newNode;
            newNode.next = tmp;
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur!=null) {
            if(cur.val==key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head==null) {
            return;
        }
        if(!contains(key)) {
            System.out.println("不存在该值");
            return;
        }
        if(head.val==key) {
            head = head.next;
        } else {
            ListNode curNode = head;
            while (curNode.next.val!=key) {
                curNode = curNode.next;
            }
            curNode.next = curNode.next.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        if(head==null) {
            return;
        }
        if(!contains(key)) {
            System.out.println("该值不存在,无法删除");
            return;
        }
        while (head!=null&&head.val==key) {
            head = head.next;
        }
        if(head!=null) {
            ListNode curNode = head;
            while (curNode.next !=null) {
                if (curNode.next.val==key) {
                    curNode.next = curNode.next.next;
                } else {
                    curNode = curNode.next;
                }
            }
        }
    }
    public ListNode reverseList() {
        if(head==null) {
            return head;
        }
        if(head.next==null) {
            return head;
        }
        ListNode curNode = head.next;
        head.next = null;
        if(curNode.next==null) {
            curNode.next = head;
            return curNode;
        }


        while(curNode!=null) {
            ListNode nextNode = curNode.next;
            curNode.next = head;
            head = curNode;
            curNode = nextNode;
        }
        return head;
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;

        while (cur!=null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {

        if(head!=null) {
            while (head!=null) {
                ListNode tmp = head.next;
                head = null;
                head = tmp;
            }
        }
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur!=null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display(ListNode pHead) {
        ListNode cur = pHead;
        while (cur!=null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int count1 = 0;
        ListNode cur = headA;
        while (cur != null) {
            count1++;
            cur = cur.next;
        }
        int count2 = 0;
        ListNode cur2 = headB;
        while (cur2 != null) {
            count2++;
            cur2 = cur2.next;
        }
        if (count1 >= count2) {
            int len = count1 - count2;
            while (len-- > 0) {
                headA = headA.next;
            }
        } else {
            int len = count2 - count1;
            while (len-- > 0) {
                headB = headB.next;
            }
        }
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        if (headA == null) {
            return null;
        }
        return null;
    }
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if(head==null||head.next==null) {
                return false;
            }
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
                if(slow==fast) {
                    return true;
                }
            }
            return false;
        }
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode dummy=new ListNode(-1);
        ListNode follow;

        if (list1.val <= list2.val) {
            dummy.next = list1;
            follow = list1;
            list1=list1.next;
        } else {
            dummy.next = list2;
            follow = list2;
            list2=list2.next;
        }
        while (list1!=null&&list2!=null) {
            if(list1.val <= list2.val) {
                follow.next = list1;
                follow = list1;
                list1 = list1.next;
            } else {
                follow.next = list2;
                follow = list2;
                list2 = list2.next;
            }
        }
        if(list1==null) {
            follow.next = list2;
        }
        if(list2==null) {
            follow.next = list1;
        }
        return dummy.next;
    }
    /*public ListNode partition(ListNode pHead, int x) {
        pHead = head;
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        // write code here
        if (pHead.val < x) {
            ListNode FrontMinNode = pHead;
            while (FrontMinNode.next != null && FrontMinNode.next.val < x) {
                FrontMinNode = FrontMinNode.next;
            }

            if (FrontMinNode.next == null) {
                return pHead;
            }
            ListNode Front = FrontMinNode;
            while (FrontMinNode.next != null) {
                if (FrontMinNode.next.val < x) {
                    ListNode tmp = FrontMinNode.next;
                    FrontMinNode.next = tmp.next;
                    ListNode tmp1 = Front.next;
                    Front.next = tmp;
                    tmp.next = tmp1;
                    Front = tmp;
                } else {
                    FrontMinNode = FrontMinNode.next;
                }
            }
        } else {
            ListNode curNode = pHead;
            ListNode rHead = null;
            while(curNode.next!=null) {
                if(curNode.next.val<x) {
                    if(pHead.val<x) {
                        ListNode tmp = curNode.next;
                        curNode.next = tmp.next;
                        ListNode tmp1 = rHead.next;
                        rHead.next = tmp;
                        tmp.next = tmp1;
                        rHead = rHead.next;
                    } else {
                        ListNode tmp = curNode.next;
                        curNode.next = tmp.next;
                        tmp.next = pHead;
                        pHead = tmp;
                        rHead = pHead;
                    }
                } else {
                    curNode = curNode.next;
                }
            }
        }
        return pHead;
    }*/
    public ListNode partition(ListNode pHead, int x) {

        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode front1 = null;
        ListNode front2 = null;
        ListNode end1 = null;
        ListNode end2 = null;
        ListNode curNode = pHead;
        while (curNode != null) {
            if (curNode.val < x) {
                if (front1 == null) {
                    front1 = curNode;
                    front2 = curNode;
                } else {
                    front2.next = curNode;
                    front2 = front2.next;
                }
            } else {
                if (end1 == null) {
                    end1 = curNode;
                    end2 = curNode;
                } else {
                    end2.next = curNode;
                    end2 = end2.next;
                }
            }
            curNode = curNode.next;
        }
        if(front2!=null) {
            front2.next = null;
        }
        if(end2!=null) {
            end2.next = null;
        }
        if (front1 == null) {
            return end1;
        }
        front2.next = end1;
        return front1;
    }

}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */